/*
 * Graph5.cpp
 *
 *  Created on: 2012-01-08
 *      Author: Anthony Varghese
 * Description: Graph example with bugs
 * 				This program is trying to
 * 				* create a graph g (on the stack) with 5 vertices and 5 edges; and remove an edge
 * 				  -- check creation of Adjacency list with fixed number of "vertices"
 * 				  -- check adding actual edges
 * 				  -- check edge removal
 * 				  -- check printing of graph
 * 				  -- check automatic deletion of stack object
 * 				* create a graph k (on the heap) with no vertices initially
 * 				  -- check creation of empty Adjacency list
 * 				  -- check adding actual edges via adding of adjacency list nodes
 * 				  -- check edge removal
 * 				  -- check printing of graph
 * 				  -- check deletion of heap object
 *              * create a graph m (on the heap) with a fixed number of vertices initially
 * 				  -- check creation of Adjacency list with fixed number of vertices
 * 				  -- check adding actual edges via adding of adjacency list nodes
 * 				  -- check edge removal
 * 				  -- check printing of graph
 * 				  -- check deletion of heap object
 * 				* create a graph h () on the heap with fixed number (test large numbers here) of vertices initially
 * 				  -- create a fixed (potentially large) number of vertices and edges
 * 				  -- check creation of a Binary tree version of the graph (eventually we want a spanning tree)
 *				Check if the graph vertices are "connected"
 */

#include <iostream>
#include <string>
#include <cstdlib> // for random numbers

#include "GraphL.h"

using namespace std;
using namespace graph;


int main(){
    cout << "Program Graph5:" << endl << endl;

	int start = 0,	end = 0;

	/*
	 * create a graph g (on the stack) with 5 vertices and 5 edges; and remove an edge
	 * 				  -- check creation of Adjacency list with fixed number of "vertices"
	 * 				  -- check adding actual edges
	 * 				  -- check edge removal
	 * 				  -- check printing of graph
	 * 				  -- check automatic deletion of stack object
	 */
	cout << "Graph g: testing a graph object with initial number of vertices" << endl;
	{
    	GraphL g( 5 );
    	g.addEdge( 1, 2, 0.4 );
    	g.addEdge( 2, 3, 0.6 );
    	g.addEdge( 2, 4, 0.1 );
    	g.addEdge( 4, 5, 0.8 );
    	g.addEdge( 3, 5, 0.2 );

    	cout << g << endl << endl;

    	cout << "    Delete an edge - start edge: "; cin >> start;
    	cout << "                       end edge: "; cin >> end;
    	g.removeEdge( start, end );

    	cout << "    After delete:" << endl << endl;
    	cout << g << endl << endl;
	}
	cout << "done with g" << endl << endl << endl;

	/*
	 * create a graph k (on the heap) with no vertices initially
	 * 				  -- check creation of empty Adjacency list
	 * 				  -- check adding actual edges via adding of adjacency list nodes
	 * 				  -- check edge removal
	 * 				  -- check printing of graph
	 * 				  -- check deletion of heap object
	 */

	cout << "Graph k: testing a graph object allocated on the heap, without initial number of vertices" << endl;
	{
    	GraphL* k = new GraphL();
    	k->addEdge( 1, 2, 0.4 );
    	k->addEdge( 2, 3, 0.6 );
    	k->addEdge( 2, 4, 0.1 );
    	k->addEdge( 4, 5, 0.8 );
    	k->addEdge( 3, 5, 0.2 );

    	cout << *k << endl << endl;
    	k->removeEdge( start, end );
    	cout << "    After delete:" << endl << endl;
    	cout << *k << endl << endl;

    	delete k;
	}
	cout << "done with k" << endl << endl << endl;


    // Ask the user for the number of vertices in the graph.
    cout << "  Enter a number and I will create another graph with that many vertices:  " << flush;
    int number_of_vertices = 0;
    cin >> number_of_vertices;

    if (number_of_vertices < 0)
    	cout << "   A graph should have 0 or more vertices.\nProgram done." << endl;
    else if (number_of_vertices == 0)
    	cout << "   A graph with no vertices is valid, but not interesting.\nProgram done." << endl;
    else {
    	/*
    	 * create a graph m (on the heap) with a fixed number of vertices initially
    	 * 				  -- check creation of Adjacency list with fixed number of vertices
    	 * 				  -- check adding actual edges via adding of adjacency list nodes
    	 * 				  -- check edge removal
    	 * 				  -- check printing of graph
    	 * 				  -- check deletion of heap object
    	 */
    	cout << "Graph m: testing a graph object allocated on the heap, with initial number of vertices set" << endl;
    	{
        	GraphL* m = new GraphL( number_of_vertices );
        	m->addEdge( 1, 2, 0.4 );
        	m->addEdge( 2, 3, 0.6 );
        	m->addEdge( 2, 4, 0.1 );
        	m->addEdge( 4, 5, 0.8 );
        	m->addEdge( 3, 5, 0.2 );

        	cout << *m << endl << endl;
        	m->removeEdge( start, end );
        	cout << "    After delete:" << endl << endl;
        	cout << *m << endl << endl;

        	delete m;
    	}
    	cout << "done with m" << endl << endl << endl;

    	/*
    	 * create a graph h () on the heap with fixed number (test large numbers here) of vertices initially
    	 * 				  -- create a fixed (potentially large) number of vertices and edges
    	 * 				  -- check creation of a Binary tree version of the graph (eventually we want a spanning tree)
    	 *				Check if the graph vertices are "connected"
    	 */
    	cout << "Graph h: testing a graph object allocated on the heap with initial num verts - with tree generated" << endl;
    	{
        	GraphL* h = new GraphL( number_of_vertices );
        	for (int i=1; i<=number_of_vertices; i++){
        		// try to have at least around two edges per vertex
        		int destination = (rand() % number_of_vertices) + 1;
        		h->addEdge( i, destination, ((float) rand() ) / ( (float) RAND_MAX ) );

        		int source = (rand() % number_of_vertices) + 1;
        		h->addEdge( source, i, ((float) rand() ) / ( (float) RAND_MAX ) );
        	}
        	cout << *h << endl << endl;

        	BinaryTree* tree = h->createTree();
        	cout << "  A tree from the graph: h " << *tree << endl << endl;
        	delete tree;
        	delete h;
    	}
    	cout << "done with h" << endl << endl << endl;
    }
	cout << "Program done." << endl;
	return 0;
}
